The ATM packet transmission protocol is described in "Asynchronous Transfer Mode-Solution for broadband ISDN", by Martin de Prycker, published by Ellis Horwood, incorporated herein by reference. Generally, a packet (termed a "cell" in ATM parlance) is addressed to a destination which is specified in the packet header by address data comprising a 12 bit Virtual Path Indicator (VPI) and a 16 bit Virtual Channel Indicator (VCI). In general terms, the VCI indicates the entire "Virtual Channel" connection route from the source to the destination through the network, via switching nodes or exchanges, whereas the VPI indicates a path through the network between nodes or switching centres of the network, which may be taken by packets forming part of several different virtual circuits. At each node, the packet arrives on an inward channel (e.g. fibre optic cable), its header is examined, and it is routed out on an outward channel in dependence upon its address data.
It is possible for each node to act in a completely predetermined manner in routing a packet on an outward channel which depends only on the address data in the packet. However, it is also possible for each node to vary the address data of a packet in passage, so as to redirect the packet on an alternative route to its destination. This is advantageous in traffic management, for example to avoid an overloaded or damaged node.
At each node, a lookup table (held, for example, in Random Access Memory (RAM)) is generally provided, the address data (i.e. VCI and VPI) in a packet being used to access the lookup table to derive the identity of the output line from the node on which the packet is to be directed towards its destination. If the node is also to vary the address data, the lookup table needs additionally to contain the new VCI and VPI address data.
In the ATM system, each packet includes address data comprising a 16 bit VCI and a 12 bit VPI. Although it would be possible to operate by merely changing the VPI, for full flexibility a node would be capable of changing both the VCI and the VPI. If the node has N input or output lines, and if the table is arranged as a `flat` lookup table with a direct one-to-one correspondence between input addresses and output addresses, the size of the table to be held at the node is N.2.sup.16.2.sup.12, and each entry in the table needs to be (16+12+log.sub.2 N) bits long. Thus, for a node to which 256 lines are connected (N=256 requiring 8 bits to encode N) , each entry in the table is (28+8=36 .times.4.5 bytes) long, and the table must contain 2.sup.36 bits=64 Gigabits so that the total size of the table needs to be 288 Gigabytes. This is a very substantial volume of memory.
One possibility is to arrange such a table as a single contiguous memory address space, with an input (address) bus to which all N input channels are connected, and an output (data) bus connected to all the outlet channels. In this case, to avoid bus contention, it would be necessary to allocate time on the input bus between the N available channels. Thus, the access time which each channel must, on average, wait to access the lookup table increases proportionately to the number of channels N, since the time available to each channel decreases in proportion to N.
As messages may be arriving through optical fibre channels at a rate of hundreds of Megabits per second, in the form of a large number of relatively short packets, it will be seen that this method very rapidly becomes unusable if it is desired to provide a large number of input and outlet channels to a node, no matter how fast individual accesses to the memory can be made.
Rather than use a single, "flat" lookup table, it may be possible to use a multiple step access, "folded" memory technique. However, multiple memory read operations take time and the arrangement of data may be less convenient for alteration or rewriting.
An alternative would be to provide each input channel with a separate lookup table. In this case, there is no bus contention for access to the lookup table, so that the access time is fast regardless of the number of the input channels. Where there are N input channels, each input channel requires a table of 1/N times the same size as that above, so that the total amount of memory required over all nodes is the same as that above. In an ATM system, with 28 bits of VPI and VCI address data, each memory thus needs to be of size 2.sup.28 * (28+logN) bits, which is 0.9 GBytes+33 MBytes * logN!. This is around the size of mainframe memories, and could require, for each input channel, of the order of 477 16Mbit memory chips.
In fact, input channels will not actually receive packets carrying the whole range of VCI and VPI addresses; the total range in each case will be smaller and it would consequently be possible to use a smaller address range (and hence a smaller table requiring a smaller volume of memory) for each input channel memory device. However, to allow for the possibility that any channel may become busy it would be necessary to provide, in each memory, an additional "overhead" volume of memory space (over and above the volume likely to be requested which is not normally used but which could occasionally be required. This overhead memory is thus needed in each input channel memory device, and hence the total memory required rises quite sharply with the number of input channels.